package leetcode_day._2023._11;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 1670.设计前中后队列
 * 算法: 队列、链表
 *
 * @author yezh
 * @date 2023/11/28 19:51
 */
public class _28 {

    static class FrontMiddleBackQueue_queue {
        // 保证 r 中的元素比 l 中的多 1 个
        Deque<Integer> l, r;

        public FrontMiddleBackQueue_queue() {
            l = new LinkedList<>();
            r = new LinkedList<>();
        }

        public void pushFront(int val) {
            l.addFirst(val);
            update();
        }

        public void pushMiddle(int val) {
            l.addLast(val);
            update();
        }

        public void pushBack(int val) {
            r.addLast(val);
            update();
        }

        public int popFront() {
            if (l.size() + r.size() == 0) return -1;
            int val = l.size() == 0 ? r.pollFirst() : l.pollFirst();
            update();
            return val;
        }

        public int popMiddle() {
            if (l.size() + r.size() == 0) return -1;
            int val = l.size() == r.size() ? l.pollLast() : r.pollFirst();
            update();
            return val;
        }

        public int popBack() {
            if (l.size() + r.size() == 0) return -1;
            int val = r.pollLast();
            update();
            return val;
        }

        void update() {
            while (l.size() > r.size()) r.addFirst(l.pollLast());
            while (r.size() - l.size() > 1) l.addLast(r.pollFirst());
        }
    }

    class Node {
        Node prev, next;
        int val;
        Node (int _val) {
            val = _val;
        }
    }
    class FrontMiddleBackQueue {
        Node he, ta, mid;
        int lsz, rsz;
        public FrontMiddleBackQueue() {
            he = new Node(-1); ta = new Node(-1);
            he.next = ta; ta.prev = he;
            mid = ta;
            lsz = rsz = 0;
        }
        public void pushFront(int val) {
            Node cur = new Node(val);
            cur.next = he.next;
            cur.prev = he;
            he.next.prev = cur;
            he.next = cur;
            lsz++;
            update();
        }
        public void pushMiddle(int val) {
            Node cur = new Node(val);
            cur.next = mid;
            cur.prev = mid.prev;
            mid.prev.next = cur;
            mid.prev = cur;
            lsz++;
            update();
        }
        public void pushBack(int val) {
            Node cur = new Node(val);
            cur.next = ta;
            cur.prev = ta.prev;
            ta.prev.next = cur;
            ta.prev = cur;
            rsz++;
            update();
        }
        public int popFront() {
            if (lsz + rsz == 0) return -1;
            int ans = he.next.val;
            he.next.next.prev = he;
            he.next = he.next.next;
            lsz--;
            update();
            return ans;
        }
        public int popMiddle() {
            if (lsz + rsz == 0) return -1;
            Node realMid = null;
            if (lsz == rsz) {
                realMid = mid.prev;
                lsz--;
            } else {
                realMid = mid;
                mid = mid.next;
                rsz--;
            }
            int ans = realMid.val;
            realMid.prev.next = realMid.next;
            realMid.next.prev = realMid.prev;
            realMid = realMid.next;
            update();
            return ans;
        }
        public int popBack() {
            if (lsz + rsz == 0) return -1;
            int ans = ta.prev.val;
            ta.prev.prev.next = ta;
            ta.prev = ta.prev.prev;
            rsz--;
            update();
            return ans;
        }
        void update() {
            while (lsz > rsz) {
                mid = mid.prev;
                lsz--; rsz++;
            }
            while (rsz - lsz > 1) {
                mid = mid.next;
                lsz++; rsz--;
            }
            if (lsz + rsz == 1) mid = ta.prev;
            if (lsz + rsz == 0) mid = ta;
        }
    }

}
